The Primordial Soup Algorithm : a systematic approach to the specification of parallel parsers

摘要

A general framework for parallel parsing is presented, which allows for a unitied, systematic approach to parallel parsing. The Primordial Soup Algorithm creates trees by allowing partial parse trees to combine arbitrarily. By adding constraints to the general algorithm, a large, class of parallel parsing strategies can be detined. This is exemplified by CYK, (hot, torn up) Earley and de Vreught & Honig parsers. From such a parsing strategy algorithms for various machine architectures can be derived in a systematic way.